package com.dragon.modules.yuegou.web;

import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.List;

/**
 * Tree的抽象实现
 * 
 * @author liuwu
 * @date 2018年3月7日
 *
 * @param <E>
 */
public abstract class AbstractTree<E> extends AbstractCollection<E> implements Tree<E> {

	@Override
	public Iterator<E> iterator() {
		return treeIterator(IteratorStrategy.BREADTH_FIRST);
	}

	@Override
	public int hashCode() {
		TreeIterator<E> itr = treeIterator(IteratorStrategy.DEPTH_FIRST);
		int hashCode = 1;
		while (itr.hasNext()) {
			E e = itr.next();
			hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
			hashCode = 31 * hashCode + itr.depth();
		}
		return hashCode;
	}

	@Override
	public boolean equals(Object o) {
		if (o == this)
			return true;
		if (!(o instanceof Tree))
			return false;
		TreeIterator<E> e1 = treeIterator(IteratorStrategy.DEPTH_FIRST);
		TreeIterator<?> e2 = ((Tree<?>) o).treeIterator(IteratorStrategy.DEPTH_FIRST);
		while (e1.hasNext() && e2.hasNext()) {
			E o1 = e1.next();
			Object o2 = e2.next();
			if (e1.depth() != e2.depth() || !(o1 == null ? o2 == null : o1.equals(o2))) {
				return false;
			}
		}
		return !(e1.hasNext() || e2.hasNext());
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		TreeIterator<E> itr = treeIterator(IteratorStrategy.DEPTH_FIRST);
		while (itr.hasNext()) {
			E e = itr.next();
			int depth = itr.depth();
			for (int i = 0; i < depth; i++) {
				builder.append("|--");
			}
			builder.append(e);
			builder.append('\n');
		}
		return builder.toString();
	}

	@Override
	public boolean containsTree(Tree<E> tree) {
		if(tree.isEmpty()) {
			return true;
		}
		Tree<E> subTree = subTree(tree.root().element());
		return tree.equals(subTree);
	}

	@Override
	public boolean containsPath(List<E> path) {
		if(path.isEmpty()) {
			return false;
		}
		TreeIterator<E> itr = treeIterator(IteratorStrategy.BREADTH_FIRST);
		int d = 0;
		while(itr.hasNext()) {
			E e = itr.next();
			E p = path.get(itr.depth());
			if(e == null ? p == null : e.equals(p)) {
				d ++;
				if(d == path.size()) {
					return true;
				}
				itr.iterateChilds();
			}else {
				itr.skipChilds();
			}
		}
		return false;
	}
	
	
}
